package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

/**
 * @author By ZengPeng
 */
public class 力扣_543_二叉树的直径 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_543_二叉树的直径().diameterOfBinaryTree(TreeNode.initRoot()));
    }

    /**
    题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

     示例 :
     给定二叉树
         1
       / \
      2   3
     / \
    4   5
     返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
     注意：两结点之间的路径长度是以它们之间边的数目表示。



    分析：【P ♥♥】
       1.递归：找到当前节点的左右子树的深度，之和为次节点的最大直接
                成员变量在外面记录最大值

    边界值 & 注意点：
       1.
     **/
    private int max=0;
    public int diameterOfBinaryTree(TreeNode root) {
        recursive(root);
        return max;
    }

    public int recursive(TreeNode root){
        //递归三步曲
        // 1.单步操作：
        // 2.终止条件：
        // 3.返回值：
        if(root==null) return 0;
        int leftLen= recursive(root.left);
        int rightLen= recursive(root.right);
        max = Math.max(max,leftLen+rightLen);
        return Math.max(++leftLen,++rightLen);
    }
}
